The present invention relates to digital communication systems generally and to a method and apparatus for acquisition of digital communication signals.
Digital communication systems transmit and receive signals which have digital information therein. Typically, such signals include the data to be transmitted plus additional portions needed to ensure accurate communication, such as synchronization signals (to synchronize the receiver with the transmitter) and error correcting codes (to ensure that the received data has not been corrupted and to correct at least part of any corrupted data).
There are many types of digital communication systems. One common one is that of a spread spectrum system. A conventional direct sequence spread spectrum signal can be viewed as the result of mixing a narrowband information-bearing signal with an informationless wideband (and constant envelope) xe2x80x9cspreadingxe2x80x9d signal. If Bi and Bp denote the bandwidths of the information-bearing signal and the spreading signal, respectively, then the xe2x80x9cprocessing gainxe2x80x9d available to the receiver is G=Bi/Bp. The receiver synchronizes the incoming signal to a locally generated version of the spreading signal and mixes the received signal with the locally generated spreading signal, thereby removing the spreading signal from the received signal and xe2x80x9ccollapsingxe2x80x9d the signal to the xe2x80x9cinformation bandwidthxe2x80x9d Bi.
The spreading signal is typically a coded sequence of some kind, such as a pseudo-random code. The United States space program initially utilized a Type 1 Reed-Muller code for deep-space communications. In code division multiple access (CDMA) systems, the code is a variation of the Reed-Muller codes.
In the IS-95 standard for CDMA systems, each user has an individual Walsh code and each base station has a pilot signal. The pilot signals of the base stations are based on a single pseudo-random code sequence but each pilot signal has a unique phase. When transmitting signals to a user, the pilot signal of the relevant base station is combined with the user""s Walsh code to produce the spreading signal for that user.
Pseudo-random code sequences are generated by pseudo-random number (PN) generators, one of which, labeled 10, is shown in FIG. 1 to which reference is now made. PN generator 10 is formed of a shift register having a series of M flip-flops 12 concatenated together via summers 14, where M is typically 15. The value of the bit stored in the ith flip-flop is ai,t which, for simplicity is labeled ai. The set of ai at any time t is the xe2x80x9cloadingxe2x80x9d of the PN generator 10 at time t.
The output ct of PN generator 10 for each time t is the value of a0 at time t, a bit of value 1 or 0. At the end of each cycle, the output ct is provided back into each summer 14 via a corresponding switch 16, thereby producing new values for the ai and a new value for ct.
Switches 16, also known as taps, have predetermined states hk and are either closed (hk=1) or open (hk=0). The initial switch ho is always closed and provides the output ct directly to the M-1th flip-flop 12. The pseudo-random code sequence p[t] is composed of PN symbols, the duration of each of which is termed a xe2x80x9cchipxe2x80x9d. Each symbol of the sequence is defined by:
xe2x80x83p[t]=(xe2x88x921)ctxe2x80x83xe2x80x83Equation 1
In order to synchronize the local version of the spreading signal with the original version, the transmitting unit additionally transmits the pilot signal, containing the code sequence. For simplicity, we assume that the transmitted signal is binary phase shift keying (BPSK) modulated.
The local unit then synchronizes its local code generator to the pilot signal after which, the local unit can despread the received information bearing signals. The pilot signal is also utilized to track variations in the transmission channel.
The received signal, after being down converted to a baseband signal and sampled at the output of a matched filter at a rate of one sample per chip is denoted by R[t] t= . . . ,xe2x88x922,xe2x88x921,0,1,2, . . . . The received signal consists of the pilot signal and the user data signals, both of which are transmitted by the transmitting unit, and interference terms caused by thermal noise and by signals transmitted by adjacent transmitting units.
For the purpose of acquiring the initial synchronization, only the pilot signal pilot[t] is of interest. For a BPSK signal, the pilot signal may be represented by:                               pilot          ⁡                      [            t            ]                          =                              ∑                          l              =              1                        F                    ⁢                      xe2x80x83                    ⁢                                    α              l                        ⁢                                          p                0                            ⁡                              [                t                ]                                      ⁢                          ⅇ                              j                ⁡                                  (                                                                                    ω                        0                                            ⁢                      l                                        +                                          φ                      i                                                        )                                                                                        Equation        ⁢                  xe2x80x83                ⁢        2            
where p0[t] is a PN sequence, xcex1lejxcfx86l is the channel gain of the l-th signal reflection (called a xe2x80x9cfingerxe2x80x9d), F denotes the number of fingers and xcfx890 denotes the residual frequency drift after baseband down-conversion. Now, consider only the most significant finger (the one with the largest xcex1l) and denote it by xcex1ejxcfx86. Also, denote the contribution of all other fingers, the user data signals and other interferences by n[t]. Then R[t] is represented by:
R[t]=xcex1p0[t]ej(xcfx890l,xcfx86)+n[t]xe2x80x83xe2x80x83Equation 3
The acquisition problem is how to efficiently obtain the phase of the PN sequence (i.e. the current loading of the PN generator 10) given some measurement record R[t] t=1,2, . . . , N.
Solutions to the acquisition problem are described in the book CDMA: Principles of Spread Spectrum Communication, by A. J. Viterbi, Addison-Wesley, 1995, in particular in section 3.4.3, pp. 58-59. The book is incorporated herein by reference.
The direct approach is to enumerate over all possible 2Mxe2x88x921 phases of the PN sequence (there are 2M possible initial loadings, but the zero loading is illegal since it produces an all zero sequence) and select the one which is optimal with respect to some criterion. This approach is computationally and time intensive due to the large number of possible PN loadings.
A possible refinement of this approach, discussed in the book CDMA: Principles of Spread Spectrum Communication, is to obtain the phase by using a two-stage (dual-dwell) search procedure, where the first stage enumerates over all possible PN phases and passes only those phases with metric values that are above some pre-specified threshold to the second stage. In the second stage, each phase hypothesis is examined more thoroughly (i.e., using a more computationally intensive criterion) in order to decide whether it is the true PN phase or not. The dual-dwell procedure is faster than the direct approach but still takes a significant amount of time.
When there is no frequency drift in the received samples R[t] (i.e., xcfx890=0), the optimal metric, under a white Gaussian noise assumption, whose absolute value needs to be maximized is a Maximum Likelihood metric, as follows:                     metric        =                              ∑                          i              =              1                        N                    ⁢                      xe2x80x83                    ⁢                                    R              ⁡                              [                t                ]                                      ⁢                          p              ⁡                              (                t                )                                                                        Equation        ⁢                  xe2x80x83                ⁢        4            
where R[1], R[2], . . . , R[N] is the block of sampled data, sampled at the rate of one sample per chip, and p[t] is one possible PN sequence. In the dual dwell procedure, the size N of the block is relatively small in the first phase and larger in the second phase.
If the data might have a frequency drift, the metric should be insensitive to frequency drifts. The following differential metric has been suggested by M. H. Zarrabizadeh and E. S. Souza in the article xe2x80x9cAnalysis of a Differentially Coherent DS-SS Parallel Acquisition Receiverxe2x80x9d, IEEE Proceedings of the 45th Vehicular Technology Conference, Vol. 2, pp. 271-275, 1995 (the article is incorporated herein by reference):                     metric        =                              ∑                          i              =              1                                      N              c                                ⁢                      xe2x80x83                    ⁢                                    z              ⁡                              [                l                ]                                      ⁢                          z              ⁡                              [                                  l                  -                  1                                ]                                                                        Equation        ⁢                  xe2x80x83                ⁢        5            
where       z    ⁡          [      l      ]        =            ∑              i        =        1                    N        c              ⁢                  R        ⁡                  [                                    lN              c                        +            t                    ]                    ⁢              p        ⁡                  [                                    lN              c                        +            t                    ]                    
NC is the number of chips used for the coherent summation (e.g. the number of chips per symbol which is 64 in the IS-95 CDMA standard), and NN is the number of z[ ] variables used for creating the final metric. For example, NN is small (e.g. 5) for the first phase (dwell) and larger (e.g. 10) for the second phase.
The following articles and patents discuss transform domain methods for soft decoding of PN loadings and error correcting codes in general when BPSK signaling is used. The articles are incorporated herein by reference.
V. V. Losev and V. D. Dvornikov, xe2x80x9cDetermination of the Phase of a Pseudorandom Sequence From its Segment Using Fast Transformsxe2x80x9d, Radio Engineering and Electronic Physics, Vol. 26, No. 8, pp. 61-66, August 1981;
M. Cohn and A. Lempel, xe2x80x9cOn Fast M-Sequence Transformsxe2x80x9d, IEEE Transactions on Information Theory, pp. 135-137, 1977;
V. V. Losev and V. D. Dvornikov, xe2x80x9cRecognition of Address Sequences Using Fast Transformationsxe2x80x9d, Radio Engineering and Electronic Physics, Vol. 28, No. 8, pp. 62-69, August 1983;
S. Z. Budisin, xe2x80x9cFast PN Sequence Correlation by Using FWTxe2x80x9d, IEEE Proceedings of the Mediterranean Electrotechnical Conference (MELECON), Lisbon, Portugal, April 1989, pp. 513-515;
Y. Be""ery and J. Snyders, xe2x80x9cOptimal Soft Decision Block Decoders Based on Fast Hadamard Transformxe2x80x9d, IEEE Transactions on Information Theory, Vol. 32, 1986, pp. 355-364; and
U.S. Pat. No. 5,463,657 to Rice.
It is an object of the present invention to provide a novel and relatively fast method and apparatus for synchronization to a pilot signal, particularly for CDMA systems.
It is a further object of the present invention to provide a method and apparatus for synchronization to a pilot signal which has a frequency drift therein.
It is a still further object of the present invention to provide a method and apparatus for soft decoding an error correcting code when frequency drift is present.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a pilot acquisition unit for code division multiple access (CDMA) communication systems which includes a fast Hadamard transform (FHT) unit and a pre-Hadamard processing unit. The FHT unit determines the quality, in accordance with a metric, of each of a set of possible pseudo-random number (PN) loadings and the pre-Hadamard processing unit generates a vector u per set of PN loadings. The vector u defines a quality metric of a received pilot signal with the set of possible PN loadings, the pre-Hadamard processing unit providing the vector u to the FHT unit.
Moreover, in accordance with a preferred embodiment of the present invention, the unit includes a partial possible PN loading generator for generating a series of partial possible PN loadings sE, wherein each partial possible PN loading sE defines one set of possible PN loadings.
Further, in accordance with a preferred embodiment of the present invention, the unit includes a dual dwell unit for selecting the PN loadings having the metric values above a predetermined threshold from among the PN loadings selected by the local PN loading selector, for determining a second metric for each of the selected PN loadings and for selecting the PN loading from among the selected PN loadings with the best value for the second metric.
Additionally, in accordance with a preferred embodiment of the present invention, the pre-Hadamard processing unit comprises a local PN generator and a u vector generator which performs the following steps:
loads a local PN generator with an initial PN loading;
loops on each of the datapoints of the received pilot signal and per loop:
combines one partial possible loading sE with a datapoint of the received pilot signal and with a PN loading produced by the local PN generator thereby to update the u vector;
steps the local PN generator to produce another PN loading; and
provides the resultant u vector to the FHT unit.
Alternatively, for received signals with frequency drift therein, the pre-Hadamard processing unit comprises a local PN generator and a u vector generator which performs a similar set of steps as follows:
loops over plurality of drift loop values, the step of looping including the steps of a) loading a local PN generator with a different initial PN loading per loop value and b) generating an input signal which is insensitive to drift from the received pilot signal;
loops on each of the datapoints of the input signal, the second step of looping including the steps of a) combining one partial possible loading sE with a datapoint of the input signal and with a PN loading produced by the local PN generator thereby to update the u vector and b) stepping the local PN generator to produce another PN loading.
The remaining steps are the same as for the non-frequency drift case.
Still further, in accordance with a preferred embodiment of the present invention, the unit can include a dual dwell unit which performs a further metric calculation on those PN loadings which produce a metric above a predefined threshold.
The present invention is operative for all digital communication systems (not just CDMA) which have frequency drifts therein and can also be implemented, as described and claimed hereinbelow, for signals encoded with error correcting codes. For the latter, the local PN generator is replaced with a generating matrix.